package lc;

import org.junit.Test;

public class Ex_offer_33 {
    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            if (postorder == null) {
                return false;
            } else if (postorder.length <= 1) {
                return true;
            }
            return dfs(0, postorder.length - 1, postorder);
        }
    
        public boolean dfs(int left, int right, int[] nums) {
            if (left >= right) {
                return true;
            }
            //根节点：最右节点
            int root = nums[right];
            int mid = -1;
            //找到右子树第一个节点
            for (int i = 0; i < right - 1; i++) {
                if (nums[i] > root) {
                    mid = i; //右子树
                    break;
                }
            }
            if (mid < 0) {
                return dfs(left, right - 1, nums);
            }
            //检测右子树[mid, right)是否全部大于根节点
            for (int i = mid; i < right; i++) {
                if (nums[i] < root) {
                    return false;
                }
            }
            return dfs(left, mid - 1, nums) && dfs(mid, right - 1, nums);
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,5,10,6,9,4,3};
        System.out.println(s.verifyPostorder(nums));
    }
}
